#!/usr/bin/perl -w
# Copyright (C) 2006, Augusto Ciuffoletti <augusto@di.unipi.it>

use strict;
use Getopt::Std;
use Data::Dumper;

srand 0;
my $gamma=5; # Weibull gamma parameter

my $usage='
Wandering token simulation with sandwich token removal.
Presented at DAPSYS. 

Usage: $0 <options>

Options:
  -h                                   this help message
  -t <simulation duration>             in time units
  -N <number of components>            in units
  -o <event duration>                  in time units
  -m <minimum interval between events> in time units
#  -M <Maximum interval between events> in time units
  -l <token loss gamma>                mean time between packet loss
  -g <token generation gamma>          mean timeout for packet generation

Copyright (C) 2006, Augusto Ciuffoletti <augusto@di.unipi.it>
';

#my $N=$ARGV[0];
#my $maxtime=1000;
#my $D_op=4;
#my $D_min=600;
#my $D_max=1800;
#my ( $N, $maxtime, $D_op, $D_min, $D_max, $D_tokenloss ) = @ARGV;



my @system=();

my @token=();

my $acc=0;
my $n_ops=0;
my $next_id=0;
my $time=0;
my $centr=0;
my $coda=0;

sub token_optimize {
# Eliminates removed tokens from token list (could be faster)
    my ( $tp ) = @_;
    my @temp=();
    my $t;   
    while ( defined($t=pop @{$tp}) ) {
	$t->{removed} || push @temp,$t;
    }
    for $t ( @temp ) {
	unshift @{$tp},$t;
    }
}

sub random_timeout {
    my ( $D_min, $g_generate ) = @_;
# Costante: esposta a sincronizzazione
#    return 2.8*$D_min;
# Weibull con gamma=5: ancora esposta a sincronizzazione
#    return $_[0]+(($D_min*3)*((-log(rand))**(1/$gamma)));
# Poisson: la migliore
#  - il minimo corrisponde a D_min
#  - il beta corrisponde al D_min per il numero dei componenti
#    che fa in modo che il valore medio del primo timeout a scadere
#    sia su 2*D_min
#    return $D_min+((2*$D_min*$D_min/$D_op)*(-log(rand)));
    return $D_min+($g_generate*(-log(rand)));
}

my %opts;
getopts('t:N:o:m:l:g:h',\%opts);
my $maxtime=(defined $opts{t})?$opts{t}:10000;
my $N=(defined $opts{N})?$opts{N}:150;
my $D_op=(defined $opts{o})?$opts{o}:4;
my $D_min=(defined $opts{m})?$opts{m}:$D_op*$N;
my $g_loss=(defined $opts{l})?$opts{l}:$maxtime;
my $g_generate=(defined $opts{g})?$opts{g}:0.01;

if ( defined $opts{h} ) {
    print $usage;
    exit 0;
}


print "Componenti = $N\n";
print "Durata     = $maxtime\n";
print "Delta_op   = $D_op\n";
print "Delta_min  = $D_min\n";
#print "Delta_max  = $D_max\n";
print "g_loss     = $g_loss\n";
print "g_generate = $g_generate\n";

for (my $i=0;$i<$N;$i++) {
    my %newcomp=(
		 id           => $i, # component id
		 last_event   => 0,  # time of last event (captured token)
		 last_token   => 0,  # last captured token
		 last_seen_ts => 0,  # time of last token passing event
		 last_seen_id => 0,  # last token passed
		 timeout      => random_timeout($D_min,$g_generate),
		 history      => [] # list of passed tokens
		 );
    push @system,\%newcomp;
}

my %newtoken=(
	      id => $next_id,  # token identifier
	      birthtime => 0,  # token birth time
	      place => 0,      # component holding the token
	      remain => 0,     # timer when token is captured (D_op)
	      removed => 0     # token removed (flag)
	      );
$next_id++;
push @token,\%newtoken;

my $idletime=0; # time with no circulating tokens
while ($time<$maxtime) {
    
    token_optimize(\@token);
    printf "$time: %d active tokens\n",$#token+1;
    if ( ($#token+1) == 0 ) {
	$idletime++;
    } else {
	if ( $idletime != 0 ) {
	    print "$time: token recovered after $idletime\n";
	    $idletime=0;
	}
    }
    
    
# Scanning all circulating tokens
  TOKEN: for my $token ( @token ) {
      my $component=$system[$token->{place}];
      printf "$time: token %d on %d\n", $token->{id}, $token->{place};
      
# Apply token removal rule (sandwich)
      my $suspect=0;
      for my $id ( @{$component->{history}} ) {
	  if ( $id < $token->{id} ) {
	      $suspect=1;
#		print "*** Suspect $token->{id} found ($id)\n";
	  }
	  if ( $suspect && ( $token->{id} == $id ) ) {
	      $token->{removed} = 1;
	      printf "$time: token %d removed by %d at age %d (sandwich)\n"
		  , $token->{id}, 
		  $token->{place}, 
		  $time - $token->{birthtime};
	      warn "*** $time: $token->{id} to remove\n";
	      next TOKEN;
	  }
      }
      
# Inject token loss event (periodic, deterministic)
      if ( ( $time != 0 ) && ( ( $time % $g_loss ) == 0  ) ) { 
# Inject token loss event (oneshot)
#	if ( $time == $g_loss ) { 
	  $token->{removed} = 1;
	  printf "$time: token %d lost by %d at age %d\n"
	      , $token->{id}, $token->{place}, $time - $token->{birthtime};
	  next TOKEN;
      }
      
# Capture the token to execute protected operation
      if ( ( $token->{remain} == 0 ) &&
	   ( $time - $component->{last_event} ) > $D_min ) 
      {
	  printf "$time: %d captures token %d\n"
	      , $token->{place}, $token->{id};
	  printf "$time: interarrival time on %d: %d\n" 
	      , $token->{place}, $time - $component->{last_event};
	  $token->{remain} = $D_op;
      }
      
# Check if token is captured
      if ( $token->{remain} > 0 ) {
	  printf "$time: event running on %d, token %d\n",
	  $token->{place},$token->{id};
	  $token->{remain}--;
	  $component->{last_event} = $time;
	  $component->{last_token} = $token->{id};
      }
      
# Token is moved to another component
      if ( $token->{remain} == 0 ) {
# Record token passage
	  ( ( ! defined $component->{history}[0] ) ||
	    ( $token->{id} != $component->{history}[0] ) ) &&
	    unshift @{$component->{history}},$token->{id};
	  $component->{last_seen_ts} = $time;
	  $component->{last_seen_id} = $token->{id};
	  $component->{timeout}= $time+random_timeout($D_min,$g_generate);
	  
	  $token->{place}=int(rand($N));
	  printf "$time: token %d passed to %d\n"
	      ,$token->{id},$token->{place};
      }
  }
    
# Controllo lo scadere del timeout di rigenerazione sui componenti
    for my $component ( @system ) {
	( $component->{last_event} == $time ) && next;
# Generazione nuovo token
	if ( $time >= $component->{timeout} ) {
	    my $newtoken={
		id => $next_id,
		birthtime => $time,
		place => $component->{id},
		remain => $D_op,
		removed => 0
		};
	    $next_id++;
#	    print Dumper($component);
#	    print Dumper($newtoken);
	    push @token,$newtoken;
	    printf "$time: token %d generated by %d after %d\n"
		,$newtoken->{id},
		$component->{id},
		$time - $component->{last_seen_ts};
	    unshift @{$component->{history}},$newtoken->{id};
	    $component->{last_event} = $time;
	    $component->{last_token} = $newtoken->{id};
	    $component->{last_seen_ts} = $time;
	    $component->{last_seen_id} = $newtoken->{id};
	    $component->{timeout}=$time+random_timeout($D_min,$g_generate);
#	    print Dumper($component);
	}
    }
    $time++;
}

# FINALE
my $activetokens=0;
for (my $i=0; $i<=$#token; $i++) {
    ( $token[$i]->{removed} == 1) && next;
    printf "token %d attivo\n",$token[$i]->{id};
    $activetokens++;
}

# print Dumper($system[113]);

print "\n==============\n";
printf "eventi %f\n",$n_ops;
printf "token attivi %d\n",$activetokens;

